/**
//给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 
//
// 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。 
//
// 
//
// 示例 1: 
//
// 
//输入: s = "anagram", t = "nagaram"
//输出: true
// 
//
// 示例 2: 
//
// 
//输入: s = "rat", t = "car"
//输出: false 
//
// 
//
// 提示: 
//
// 
// 1 <= s.length, t.length <= 5 * 10⁴ 
// s 和 t 仅包含小写字母 
// 
//
// 
//
// 进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？ 
// Related Topics 哈希表 字符串 排序 👍 565 👎 0

*/

package com.xixi.basicAlgroithms.sort;

public class ID00242ValidAnagram {
public static void main(String[] args) {

    Solution solution = new ID00242ValidAnagram().new Solution();
    System.out.println(solution.isAnagram("anagram","nagaram"));
}


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean isAnagram(String s, String t) {

        if(s.length() != t.length()) return false;

        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();

        quickSort(sChars, 0, s.length() -1);
        quickSort(tChars, 0, t.length() -1);


        for(int i = 0; i < s.length(); ++i){
            if(sChars[i] != tChars[i]) return false;
        }

        return true;



    }

    public char[] quickSort(char[] chars, int start, int pivot){

        if(start > pivot){
            //如果初始坐标大于分割坐标，就说明已经递到底了
            return chars;
        }

        int nextPiovt = partition(chars, start, pivot);

        //将分开的两段分片再次按大小放置
        quickSort(chars, start, nextPiovt - 1);
        quickSort(chars, nextPiovt + 1 , pivot);



        return chars;
    }


    public  int partition(char[] chars, int start, int pivot){
        char pivotValue = chars[pivot]; //设定分隔值,小于此值的，放前面，大于此值的，放后面。每递一层，初筛一次。
        int nextPivot = start; //通过不断前移nextPivot来分隔已经粗分好的大小数组
        for(int index = start; index < pivot; ++index){
            if(chars[index] < pivotValue){ //如果chars[index]小于pivotValue,，
                swap(chars,nextPivot, index);//就交换当前nextPivot的值和index指针的值，相当于把当前index的值放到nextPivot前面
                ++nextPivot;
            }//如果碰到大于pivotValue的值，就停止nextPivot，这时候nextPivot就相当于停下来了，等待碰到小值交换

        }
        swap(chars, nextPivot, pivot); //最后，不要忘了把nextPivot和pivot的值对调，这样才真正完成了排序，最后nextPivot停下来的值肯定大于等于pivot
        return nextPivot;

    }


    public  void swap(char[]a, int i , int j){
        char tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

}
//leetcode submit region end(Prohibit modification and deletion)




}